# -*- coding: utf-8 -*-            
# @Time : 2023/12/20 22:50
# @Author  : lining
# @FileName: 删除二叉搜索树节点.py
"""
https://leetcode.cn/problems/delete-node-in-a-bst/
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。
输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
二叉搜索树删除节点，没有重复节点
1：删除叶子节点，直接删除
2；删除节点只有一个子节点，把子节点改成父节点的子节点
3：删除节点有两个子节点，从他右子树中找到最小的点，和他替换，最小的点肯定没有左子树

"""
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


node10 = TreeNode(14)
node5 = TreeNode(7)
node6 = TreeNode(9)
node2 = TreeNode(8, node5, node6)
node7 = TreeNode(11)
node8 = TreeNode(13, node10)
node3 = TreeNode(12, node7, node8)
# 根
node4 = TreeNode(10, node2, node3)
node9 = TreeNode(0)


class DelNode():
    """
    先找到点，如果没有叶子节点，直接删除
    有一个叶子节点，直接把叶子节点顶上来
    """
    def __init__(self):
        pass

    def del_node(self, node, val):
        """
        value:要删除的值
        node:当前遍历到的点
        """
        if node is None:
            print('没有这个节点')
            # 找不到节点
            return node
        if val < node.val:
            node.left = self.del_node(node.left, val)
        elif val > node.val:
            node.right = self.del_node(node.right,val)
        else:
            if node.left is None and node.right is None:
                return None
            # 只有一个子节点
            elif node.left is None or node.right is None:
                return node.left or node.right
            else:
                current = node
                node = node.right
                while node.left:
                    node = node.left
                # 递归着做，如果右子树没有左子树，也可以直接返回右子树，再把原来的左子树变成右子树的左子树
                current.right = self.del_node(current.right, node.val)
                current.val = node.val
                return current
        return node


a = DelNode().del_node(node4,12)
print(a)

